题目 | 难度 |
---|---|
剑指 Offer 04. 二维数组中的查找 | 中等 |
剑指 Offer 11. 旋转数组的最小数字 | 简单 |
剑指 Offer 53 - I. 在排序数组中查找数字 I | 简单 |
剑指 Offer 53 - II. 0~n-1中缺失的数字 | 简单 |
# 1. 二维数组中的查找
题目
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
基本实现
二维数组是有序的,比如下面的数据:
1 2 3
4 5 6
7 8 9
var arr = [[1,2,3],[4,5,6],[7,8,9]]
console.log(arr[2][0]); //7
console.log(arr.length); //4
2
3
4
5
6
7
代码思路:
将二维数组看作平面坐标系
从左下角(0,arr.length-1)
开始比较:
目标值大于坐标值---
x坐标+1
目标值小于坐标值---
y坐标-1
注意:
二维数组arr[i][j]
中,j
代表x
坐标,i
代表y
坐标
function Find(target, array) {
let i = array.length - 1; // y坐标
let j = 0; // x坐标
return compare(target, array, i, j);
}
function compare(target, array, i, j) {
if (array[i] === undefined || array[i][j] === undefined) {
return false;
}
const temp = array[i][j];
if (target === temp) {
return true;
}
else if (target > temp) {
return compare(target, array, i, j+1);
}
else if (target < temp) {
return compare(target, array, i-1, j);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2. 旋转数组的最小数字
题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组[3,4,5,1,2]
为[1,2,3,4,5]
的一次旋转,该数组的最小值为 1。
示例 :
输入:numbers = [2,2,2,0,1]
输出:0
输入:numbers = [3,4,5,1,2]
输出:1
2
3
4
5
思路:
旋转数组其实是由两个有序数组拼接而成的,因此可以使用二分法,只需要找到拼接点即可。
数组中点 mid = Math.floor(low+high)/2
array[mid] > array[high]
:出现这种情况的
array
类似[3,4,5,6,0,1,2]
,此时最小数字一定在mid
的右边。low = mid + 1
array[mid] == array[high]
:出现这种情况的
array
类似[1,0,1,1,1]
或者[1,1,1,0,1]
,此时最小数字不好判断在mid
左边 还是右边,这时只好一个一个试 。high = high - 1
array[mid] < array[high]
:出现这种情况的
array
类似[2,2,3,4,5,6,6]
,此时最小数字一定就是array[mid]
或者在mid
的左边。因为右边必然都是递增的。high = mid
function minNumberInRotateArray(arr) {
if (arr.length == 0) return 0;
let low = 0,
high = arr.length - 1;
while (low < high) {
let mid = Math.floor((high + low) / 2);
if (arr[mid] > arr[high]) {
low = mid + 1;
} else if (arr[mid] == arr[high]) {
high = high - 1;
} else {
high = mid;
}
}
return arr[low];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 3. 在排序数组中查找数字 I
「剑指 Offer 53 - I. 在排序数组中查找数字 I」
题目
统计一个数字在排序数组中出现的次数。
思路:
已经排序好的数组,推荐使用二分搜索。
先用二分搜索找到目标数的一个索引,再从两边扩散,统计数量。
若二分查找没找到目标数,直接返回0
。
const search = (nums, target) => {
// 定义上下限、找到的标志flag
let [low, high, flag] = [0, nums.length - 1, null];
while (low <= high) {
const mid = Math.floor((low + high)/2);
if (nums[mid] > target) {
high = mid - 1;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
// 如果找到了,将mid赋值给flag,存的是索引
flag = mid;
// 找到一个,直接退出循环
break;
}
}
// while结束后,判断是否找到,没找到直接返回0
if (flag === null) return 0;
// 从flag开始,向两边扩散
low = high = flag;
while (nums[low - 1] === target) low--;
while (nums[high + 1] === target) high++;
// 返回计数
return high - low + 1;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 4. 0~n-1中缺失的数字
「剑指 Offer 53 - II. 0~n-1中缺失的数字」
题目
一个长度为n-1
的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1
之内。在范围0~n-1
内的n
个数字中有且只有一个数字不在该数组中,请找出这个数字。
思路:
- 有序数组 ——> 二分查找
nums[mid] === mid
:左半边完整,缩小范围,开始找右半边nums[mid] !== mid
:左半边不完整,缩小范围,在左半边找
const missingNumber = nums => {
let [low, high] = [0, nums.length - 1];
while (low <= high) {
const mid = (low + high) >> 1;
if (nums[mid] === mid) {
// 左半边是完整的
low = mid + 1;
} else {
// 左半边不完整
high = mid - 1;
}
}
return low;
};
2
3
4
5
6
7
8
9
10
11
12
13
14